package algorithms.question.class22;

import common.util.MyUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * https://leetcode-cn.com/problems/tallest-billboard/
 *
 * @author guichang
 * @date 2021/8/27
 */

@SuppressWarnings("all")
public class Code5_最高的广告牌 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createArray(1, 2, 3, 6);
        MyUtil.print(tallestBillboard(nums));
    }

    public static int tallestBillboard(int[] rods) {
        if (rods == null || rods.length < 2) {
            return 0;
        }
        // 差值为key的集合最小累加和为value
        // key相同则保留value较大的
        Map<Integer, Integer> dp = new HashMap<>(), cur;
        dp.put(0, 0);// 空集合
        for (int n : rods) {
            if (n == 0) {
                // 0无意义
                continue;
            }
            // 临时记录dp的深拷贝
            cur = new HashMap<>(dp);
            cur.forEach((k, v) -> {
                int max = k + v; // 集合中较大的
                int min = v; // 集合中较小的

                // 当前数与集合中较大的的结合
                int p1 = k + v + n;
                int max1 = p1;
                int min1 = v;
                // 很明显max1必定大于min
                dp.put(max1 - min1, Math.max(min1, dp.getOrDefault(max1 - min1, 0)));

                // 当前数与集合中较小的数结合，需要判断新的大值是否比旧的大值大
                int p2 = min + n;
                int max2 = k + v > p2 ? max : p2;
                int min2 = k + v > p2 ? p2 : max;
                dp.put(max2 - min2, Math.max(min2, dp.getOrDefault(max2 - min2, 0)));
            });
        }
        // 差值为0的就是我们要的
        return dp.get(0);
    }

}